/*
 ***********************************************************************
 *                                                                     *
 *                     Binary Tree Routines Library                    *
 * Unit Tests                                                          *
 * Author: Arash Partow - 2001                                         *
 * URL: http://www.partow.net                                          *
 *                                                                     *
 * Copyright notice:                                                   *
 * Free use of the Binary Tree Routines Library is permitted under the *
 * guidelines and in accordance with the most current version of the   *
 * Common Public License.                                              *
 * http://www.opensource.org/licenses/cpl1.0.php                       *
 *                                                                     *
 ***********************************************************************
*/

#include <iostream>
#include <string>

#include "binary_tree.hpp"

void test01()
{
   std::cout << "---[ test01 ]---" << std::endl;
   const int max_elements = 10;
   binary_tree::node<int,int>::node_ptr head = 0;
   binary_tree::init(&head,0,0);

   for(int i = 1; i < max_elements; ++i)
   {
      head = insert(head,i,i);
   }

   head = binary_tree::balance(head);
   recompute_depths(head);

   for(int i = 0; i < max_elements; ++i)
   {
      if (!binary_tree::exists(head,i))
      {
         std::cout << "test01() - Error: could not find " << i << std::endl;
      }
   }

   for(int i = max_elements; i < 2 * max_elements; ++i)
   {
      if (binary_tree::exists(head,i))
      {
         std::cout << "test01() - Error: found an element that should not exist!  value:" << i << std::endl;
      }
   }

   binary_tree::free(head);
   std::cout << "----------------\n\n";
}

void test02()
{
   std::cout << "---[ test02 ]---" << std::endl;

   const int max_elements = 10;
   binary_tree::node<int,int>::node_ptr head = 0;

   binary_tree::init(&head,0,0);
   for(int i = 1; i < max_elements; ++i)
   {
      head = insert(head,i,i);
   }

   head = binary_tree::balance(head);
   recompute_depths(head);

   std::cout << "preorder" << std::endl;
   binary_tree::preorder_display(head);
   std::cout << "---------------" << std::endl;
   std::cout << "inorder" << std::endl;
   binary_tree::inorder_display(head);
   std::cout << "---------------" << std::endl;
   std::cout << "postorder" << std::endl;
   binary_tree::postorder_display(head);
   std::cout << "---------------" << std::endl;

   binary_tree::free(head);
   std::cout << "----------------\n\n";
}

void test03()
{
   std::cout << "---[ test03 ]---" << std::endl;

   const int max_elements = 10000;
   binary_tree::node<int,int>::node_ptr head = 0;

   binary_tree::init(&head,0,0);
   for(int i = 1; i < max_elements; ++i)
   {
      head = insert(head,i,i);
   }

   unsigned int total_hop_count = 0;

   for(int i = 0; i < max_elements; ++i)
   {
      unsigned int current_hop_count = 0;
      binary_tree::exists(head,i,current_hop_count);
      total_hop_count += current_hop_count;
   }

   std::cout << "Total hop count before balance: " << total_hop_count << std::endl;

   head = binary_tree::balance(head);
   recompute_depths(head);

   total_hop_count = 0;

   for(int i = 0; i < max_elements; ++i)
   {
      unsigned int current_hop_count = 0;
      binary_tree::exists(head,i,current_hop_count);
      total_hop_count += current_hop_count;
   }

   std::cout << "Total hop count after balance:  " << total_hop_count << std::endl;

   binary_tree::free(head);

   std::cout << "----------------\n\n";
}

void test04()
{
   std::cout << "---[ test04 ]---" << std::endl;

   const int max_elements = 1000;
   binary_tree::node<int,int>::node_ptr head = 0;
   binary_tree::init(&head,0,0);
   for(int i = 1; i < max_elements; ++i)
   {
      head = insert(head,i,i);
   }

   head = binary_tree::balance(head);

   for(int i = max_elements - 1; i >= 0 ; --i)
   {
      if (!binary_tree::exists(head,i))
      {
         std::cout << "test04() - Error: could not find " << i << std::endl;
      }

      head = binary_tree::delete_node(head,i);

      if (binary_tree::exists(head,i))
      {
         std::cout << "test04() - Error: found an element that should not exist!  value:" << i << std::endl;
      }
   }

   binary_tree::free(head);
   std::cout << "----------------\n\n";
}

void test05()
{
   std::cout << "---[ test05 ]---" << std::endl;

   static const int max_elements = 20;
   binary_tree::node<int,int>::node_ptr head = 0;

   binary_tree::init(&head,0,0);
   for(int i = 1; i < max_elements; ++i)
   {
      head = insert(head,i,i);
   }

   std::cout << "Before balance: " << std::endl;
   binary_tree::topological_display(head);
   std::cout << "Max depth: " << binary_tree::max_depth(head) << std::endl;
   std::cout << "Min depth: " << binary_tree::min_depth(head) << std::endl;

   std::cout << "---------------" << std::endl;

   head = binary_tree::balance(head);
   recompute_depths(head);

   std::cout << "After balance: " << std::endl;
   binary_tree::topological_display(head);
   std::cout << "Max depth: " << binary_tree::max_depth(head) << std::endl;
   std::cout << "Min depth: " << binary_tree::min_depth(head) << std::endl << std::endl;

   binary_tree::free(head);
   std::cout << "----------------\n\n";
}

int main(void)
{
   test01();
   test02();
   test03();
   test04();
   test05();
   return 0;
}
